#include "stdio.h"
#include "unistd.h"
#include "malloc.h"
/*图的邻接矩阵*/
#define MaxVertexNum 50
#define INT_MAX = 32677
typedef char VertexType;
typedef int Adjmatrix;
typedef struct
{
  VertexType vexs[MaxVertexNum];
  Adjmatrix arcs[MaxVertexNum][MaxVertexNum]; //邻接矩阵，假定为int型。
} Mgraph;

void CreateMGraph(Mgraph *G, int n, int e)
{
  int i, j, k, w;
  scanf("%d,%d", &n, &e); //读入顶点数和边数。
  for (i = 0; i < n; i++)
  {
    scanf("%c", &G->vexs[i]);
  }
  for (i = 0; i < n; i++)
  {
    for (j = 0; j < n; j++)
    {
      G->arcs[i][j] = INT_MAX; //初始化邻接矩阵为无穷大
    }
  }
  for (k = 0; k < e; k++)
  {
    scanf("%d,%d,%d", &i, &j, &w);
    G->arcs[i][j] = w;
    G->arcs[j][i] = w; //置矩阵对称元素权值
  }
}

/*邻接表存储结构*/
#define MaxVertexNum 20     //
typedef char VertexType;
typedef struct node
{             //边表结点类型
  int adjvex; //顶点的序号。
  struct node *next;
} EdgeNode;
typedef struct vnode
{
  VertexType vertex;            //顶点域，
  EdgeNode *link;               //边表头指针
} VNode, Adjlist[MaxVertexNum]; //邻接表
typedef Adjlist ALGraph;        //定义为图类型

/*创建无向图邻接表的建表算法*/
void CreateGraph(ALGraph GL, int n, int e)
{
  int i, j, k;
  EdgeNode *p;
  for (i = 0; i < n; i++)
  {
    GL[i].vertex = getchar(); //读入顶点信息
    GL[i].link = NULL;        //边表头指针置空
  }
  for (k = 0; k < e; k++)
  {
    scanf("%d,%d", &i, &j); //采用头插法建立每个顶点的邻接表
    p = (EdgeNode *)malloc(sizeof(EdgeNode));

    p->adjvex = j; //
    p->next = GL[i].link;
    GL[i].link = p;
    p = (EdgeNode *)malloc(sizeof(EdgeNode));

    p->adjvex = i;        // 将邻接点序号i赋给新结点的邻接点域
    p->next = GL[j].link; //

    GL[j].link = p; //将新结点插入到订单vj的边表头部。
  }
}

/*邻接矩阵为存储结构的深度优先搜索遍历算法 */
int visited[20];
void DFS(MGraph G, int i, int n)
{
  int j;
  printf("v%d->", i);
  visited[i] = 1; //标记vi已访问过
  for (j = 0; j < n; j++)
  {
    if (G.arcs[i][j] == 1 && !visited[j])
    {
      DFS(G, j, n); // 若（vi,vj)属于E(G),且vj未被访问过，则从开始递归调用
    }
  }
}

/*以邻接表为存储结构的深度优先搜索遍历算法*/
int visited[20];
void DFS1(AlGraph G, int i)
{
  EdgeNode *p;
  int j;
  printf("v%d->", i); //假定访问顶点vi以输出该订单的序号代之
  visited[i] = 1;     //标记vi已访问过
  p = G[i].link;      //取vi邻接表的表头指针

  while (p != NULL)
  {
    j = p->adjvex; //j为vi的一个邻接点序号
    if (!visited[j])
    {
      DFS1(G, j);
    }
    p = p->next;
  }
}

/*以邻接矩阵为存储结构的广度优先搜索*/
void BFS(MGraph G, int i, int n)
{
  CirQueue Q;
  int k, j;
  InitQueue(&Q);
  printf("v%d->", i);
      visited[i] = 1;
  EnQueue(&Q, i);
  while (!QueueEmpty(&Q))
  {
    k = DeQueue(&Q);
    for (j = 0; j < n; j++)
    {
      if (G.arcs[k][j] == 1 && !visited[j])
      {
        printf("v%d->", j);
        visited[j] = TRUE;
      }
    }
  }
}

/**以邻接表为存储结构的广度优先搜素遍历算法*/
void BFS1(ALGraph G, int i, int n)
{
  CirQueue Q;
  int j, k;
  InitQueue(&Q);
  EdgeNode *p;
  int visited[20];
  printf("v%d->", i);
  visited[i] = 1;
  EnQueue(&Q, i);
  while (!QueueEmpty(&Q))
  {
    k = DeQueue(&Q);
    p = G[k].link;
    while (p != NULL)
    {
      j = p->adjvex;
      if (!visited[j])
      {
        printf("v%d->", j);
        virtual[j] = 1;
        EnQueue(&Q, j);
      }
      p = p->next;
      /* code */
    }

    /* code */
  }
}